//============================================================================
// Name        : 6_1_Linux.cpp
// Author      : Eric Chen
// Version     :
// Copyright   : Your copyright notice
// Description : Building a heap using insertion, Ansi-style
//============================================================================
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

int SimapleArray[]={5,3,17,10,84,19,6,22,9};

class PrintInt
{
	public:
		void operator()(int elem) const
		{
			cout << elem<<' ';
		}
};

//i starts from one
void heap_increase_key(vector<int>& vec,int i, int key)
{
	if(key<vec[i-1])
	{
		cout<<"new key is smaller than current key\n";
		return;
	}
	for(vec[i-1]=key;
			i>0&&vec[(i-1)/2]<vec[i-1];
			i=(i+1)/2)
		swap(vec[i-1],vec[(i-1)/2]);
}
void max_heap_insert(vector<int>& vec,int key)
{
	vec.push_back(numeric_limits<int>::min());
	heap_increase_key(vec,vec.size(),key);
}

void build_max_heap_insertion(vector<int>& vec)
{
	vector<int> temp(vec);
	int size=vec.size();
	vec.clear();
	vec.push_back(temp[0]);
	for(int i=1;i<size;++i)
	{
		max_heap_insert(vec,temp[i]);
	}
}
int main (int argc, char * const argv[]) {
    // insert code here...
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
    cout << "Array before sorting\n";
    for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	build_max_heap_insertion(A);
	cout << "Array after sorting\n";
	for_each(A.begin(), A.end(), PrintInt());

	cout<<endl;

    return 0;
}

